package io.vector.study.algorithm.heap;

/**
 * Created by vector on 2017/3/15.
 */
public class MinHeap<E extends Comparable<? super E>> extends AbstractHeap<E> implements Heap<E> {

    @Override
    protected void percolateUp(int index) {
        int hole = index;
        int parentIndex;

        while (hasParent(hole)) {
            parentIndex = parentIndex(hole);
            if (compareByIndex(hole, parentIndex) >= 0) {
                break;
            }

            swap(hole, parentIndex);
            hole = parentIndex;
        }
    }

    @Override
    protected void percolateDown(int index) {
        int rootIndex = index;
        int leftChildIndex, rightChildIndex, minChildIndex;

        while (hasChild(rootIndex)) {
            leftChildIndex = leftChildIndex(rootIndex);
            minChildIndex = leftChildIndex;
            rightChildIndex = rightChildIndex(rootIndex);

            if (isValidIndex(rightChildIndex) && compareByIndex(rightChildIndex, minChildIndex) < 0) {
                minChildIndex = rightChildIndex;
            }

            if (compareByIndex(rootIndex, minChildIndex) < 0) {
                break;
            }

            swap(rootIndex, minChildIndex);
            rootIndex = minChildIndex;
        }
    }

}
